import java.util.Deque;
import java.util.LinkedList;

public class Leetcode98 {
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        int current = Integer.MIN_VALUE;
        boolean first = true;

        Deque<TreeNode> stk = new LinkedList<>();
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            if (current < root.val || first) {
                current = root.val;
                first = false;
            } else {
                return false;
            }
            root = root.right;
        }

        return true;
    }

}
